package hash.medium;

import java.util.HashMap;
import java.util.Map;

/**
 * 复制带随机指针的链表
 * 示例 1:
 *
 * 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
 * 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
 * 示例 2：
 * 输入：head = [[1,1],[2,1]]
 * 输出：[[1,1],[2,1]]
 * 示例 3：
 * 输入：head = [[3,null],[3,0],[3,null]]
 * 输出：[[3,null],[3,0],[3,null]]
 * 示例 4：
 *
 * 输入：head = []
 * 输出：[]
 * 解释：给定的链表为空（空指针），因此返回 null。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer
 */
public class CopyListWithRandomPointer_138 {

    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
        Node dummy = new Node(-1);
        Node curNode = dummy, tail = head;
        while(tail != null) {
            Node n = new Node(tail.val);
            //[1, 2] [23, null] [1, 0]
            map.put(tail, n);
            curNode.next = n;
            curNode = curNode.next;
            tail = tail.next;
        }
        curNode = dummy.next;
        while (head != null) {
            if (head.random != null) {
                curNode.random = map.get(head.random);
            }
            curNode = curNode.next;
            head = head.next;
        }
        return dummy.next;
    }

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
}
